// quick sort 快速排序代码示例。
// 快速排序采用分治（ Divide and Conquer ）的思想，
// ■ 假设按照从小到大的顺序排序，从数组中选取一个基数，此时数组是一个区间，
// ■ 分区过程，将数组中比这个数大的排在右边，比这个数的小的排在左边，这样数组被这个基数分成了左右两个区间，
// ■ 再对分割的左右两部分分别选取基数，然后再重复分区过程，直到各部分只有一个数，
// ■ 基数的选取会影响算法的复杂度，简单点可以选取区间中第一个元素。
// 快速排序是不稳定排序方法（无法保证相同的值的前后顺序），
// 平均时间复杂度 O(N*logN) ，最坏时间复杂度 O(N^2) 。
#include <stdio.h>

// 对数组 left ~ right 范围内的元素按照从小到大顺序排序。
static void 
_QuickSort(int *arr, int left, int right) {
    if (left < right) {  
        // Swap(arr[left], arr[(left + r) / 2]); //将中间的这个数和第一个数交换，这样就选取了中间的数作为基数。
        int i = left, j = right, base = arr[left];  
        // 小于 base 的值排在左边，大于 base 的值排在右边
        while (i < j) {  
            while(i < j && arr[j] >= base) // 从右向左找第一个小于 base 的数
                j--;    
            if(i < j)   
                arr[i++] = arr[j];  
              
            while(i < j && arr[i] < base) // 从左向右找第一个大于等于 base 的数
                i++;    
            if(i < j)   
                arr[j--] = arr[i];  
        }  
        arr[i] = base; // i 等于 j 此时就是基数的索引

        _QuickSort(arr, left, i - 1); // 递归调用
        _QuickSort(arr, i + 1, right);
    }  
}

void 
QuickSort(int *arr, int len) {
    _QuickSort(arr, 0, len - 1);
}

int
main() {
    int arr[] = {1000, 100, -100, 0, 300, 4000, -50, -20, -1000, 1000};
    int len = sizeof(arr)/sizeof(arr[0]);

    for (int i = 0; i < len; i++)
        printf("%d ", arr[i]);
    QuickSort(arr, len);
    printf("\nafter sorting:\n");
    for (int i = 0; i < len; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}
